1. Field
One or more embodiments relate to a path-finding system, and more particularly to an apparatus and method for generating and using an obstacle-avoidance path in a grid map.
2. Description of the Related Art
A path for movement of a mobile object, such as a mobile robot, is generally set using a grid map. The grid map divides a surrounding area in which the mobile object moves into smaller definable areas or grids and may represent the possibility of the existence of an object in each grid using a definable probability. In order to move to a specific location, the mobile object moves to the location along a path, using the grid map, such that it does not collide with obstacles. A conventional specific location that may be of interest for mobile robots, such as cleaning robots, is a charging station for automatic charging or a specific location for a particular task.
In general, a shortest path from an origin to a destination is typically desirably found during the generation of a path to be used by the mobile object, and thus many, if not all, available paths from the origin to the destination are sequentially examined. When a grid map is not large, the amount of calculations for such path-finding is typically not too large for an appropriate path to be rapidly generated. However, the larger the grid map, the greater the number of grids. Thus, required amounts of memory and calculations increase in proportion to the size of the grid map. Consequently, it becomes difficult for an apparatus having a limited memory or processing capacity, such as with an embedded system, to rapidly find the appropriate path.